The present invention relates to computer systems, and more particularly to a method and system for testing filter rules by caching the results of a search of a decision tree such as a software managed tree, ternary CAM search, or other search in which keys are tested by rules with numerical ranges of application.
FIG. 1 depicts conventional networks 10 and 20 which may be connected to the Internet 30. Each network 10 and 20 includes host (or several hosts) 12, 14 and 16 and 22 and 24, respectively. Each network 10 and 20 also includes a switch (or several switches) 18 and 26, respectively, and may include one or more servers such as the servers 17, 19 and 28, respectively. In addition, each network 10 and 20 may include one or more gateways 13 and 25, respectively, to the Internet 30. Not explicitly shown are routers and other portions of the networks 10 and 20 which may also control traffic through the networks 10 and 20 and which will be considered to be inherently depicted by the switches 18 and 26, respectively, and the networks 10 and 20 in general.
In order to manage communications in a network, such as the network 10 or 20, filter rules are used. Filter rules are typically employed by switches of the network. A filter rule tests packets which are being transmitted via a network in order to provide a variety of services. A filter rule may test packets entering the network from an outside source to ensure that attempts to break into the network can be thwarted. For example, traffic from the Internet 30 entering the network 10 may be tested in order to ensure that packets from unauthorized sources are denied entrance. Similarly, packets from one portion of a network may be prevented from accessing another portion of the network. For example, a packet from some of the hosts 12, 14 or 16 may be prevented access to either the server 17 or the server 19. The fact that the host attempted to contact the server may also be recorded so that appropriate action can be taken by the owner of the network. Filter rules may also be used to transmit traffic based on the priorities of packets. For example, packets from a particular host, such as the host 12, may be transmitted because the packets have higher priority even when packets from the hosts 14 or 16 may be dropped. Filter rules may also be used to ensure that new sessions are not permitted to be started when congestion is high even though traffic from established sessions is transmitted. Other functions could be achieved based on the filter rule. Filter rules can also interact, based on the priority for the filter rule. For example, a first filter rule may be a default filter rule, which treats most cases. A second filter rule can be an exception the first filter rule. The second filter rule would typically have a higher priority than the first filter rule to ensure that where a packet matches both the first and the second filter rule, the second filter rule will control.
Filter rules test a key in order to determine whether the filter rule will operate on a particular packet. The key that is typically used is the Internet Protocol (IP) five-tuple of the packet. The IP five-tuple typically contains five fields of interest: the source address, the destination address, the source port, the destination port and the protocol. These fields are typically thirty-two bits, thirty-two bits, sixteen bits, sixteen bits and eight bits, respectively. Thus, the part of IP five-tuple of interest is typically one hundred and four bits in length. Filter rules typically utilize these one hundred and four bits, and possible more bits, in order to perform their functions. For example, based on the source and destination addresses, the filter rule may determine whether a packet from a particular host is allowed to reach a particular destination address.
Furthermore, the key often contains additional bits other than the fields of the IP five-tuple. For example, a TCP SYN (start of session) packet, which starts a session, may be characterized differently than a TCP packet for an existing session. This characterization is accomplished using bits in addition to those in the IP five-tuple. The additional bits may be used by a filter rule which manages traffic through a network. For example, when the network is congested, the filter rule may proactively drop the TCP SYN packet while transmitting TCP packets for existing sessions. These operations allow the network to continue to operate and help reduce congestion. In order to perform this function, however, the filter rule utilizes a SYN packet or the additional bits which characterize a packet as a start packet or a packet from an existing session. Thus, the filter rules typically operate using a key that includes at least some fields of the IP five-tuple of a packet and may include additional bits.
In order to manage traffic over a network, such as the network 10, multiple filter rules are typically used. In addition, different types of filter rules may be used. The type of the filter rule is determined by the type of action which a filter rule may take if a key matches the filter rule. For example, one type of action may be permit or deny. Based on the key, such a filter rule determines whether to permit or deny access of a particular packet to a portion of the network. Another type of action may be a quality of service. For example, the network may provide five levels of service. When the key matches a filter rule of this type, the quality of service for the packet is determined to be one of the five possible levels of service. Yet another type of filter rule may be to tag or not tag a particular packet. Thus, based on whether the key for a packet matches a filter rule of this type, a bit may be set in an extended key or the packet five-tuple. Within each type of filter rule, different filter rules may also have different priorities. Thus, if a key matches more than one filter rule in a particular type, the action(s) to be taken can be determined based on the priorities of the filter rules matched.
Each of the filter rules, regardless of type, typically utilizes one of two criteria for testing keys. One category of filter rule utilizes an exact match. The filter rule operates on a packet if the key or a field of the key for the packet exactly matches the criteria for the filter rule. If no exact match exists, then the filter rule is not invoked. Such a filter rule is relatively easy to test keys against.
The second category of filter rule utilizes one or more ranges of values against which a key is tested. One criterion for such a filter rule is typically a range of values for a field of a key. For example, if a key utilizes the IP five-tuple, the criteria for the filter rule would typically include a range of values for one or more of the five fields of the IP five-tuple. The values for each of the fields are determined by converting the bits in a field to a binary number. For example, the thirty-two bit source address field can be converted into an integer between zero (all bits of the thirty-two bit binary number are zeroes) and over four billion (all thirty-two bits of the binary number are ones). The filter rule is tested by determining whether keys for incoming packets have values that are within the ranges for the appropriate field.
A particular filter rule may use an exact match for each field of a key, may use ranges for each field of a key, or may use some combination of the two. The filter rule is tested by determining whether the key meets the criteria of the filter rule for each field. Where a filter rule uses a range of values as a criterion for the field, that portion of the filter rule is tested by determining whether the corresponding field of the key fits within the range of values. Where a filter rule requires an exact match for a field, that portion of the filter rule is tested by determining whether the corresponding field of the key exactly matches the value of the filter rule.
A set of filter rules used in a system may include interval-based filter rules and may include multiple types of filter rules having differing priorities. One of ordinary skill in the art will readily recognize that such a set of filter rules is difficult to test. Typically, each filter rule in the set is tested against the key. The filter rules are also typically tested in order, based on the priorities of the filter rules. Furthermore, filter rules of each type are tested. Explicitly testing such a large number of filter rules may be expensive and time-consuming. Furthermore, interval-based filter rules are tested against a particular key by determining whether the field of the key is within the corresponding range of values for that field. The range of values for the field may be quite large. In order to explicitly test the key against this range of values, a structure which consumes a relatively large amount of memory must be built. In addition, such a test often requires a relatively large amount of time to complete. Thus, such a filter rule is expensive both in terms of time and memory. It is, therefore, expensive to test a number filter rules which may have different types, may have different priorities and which may be interval-based.
Accordingly, what is needed is an improved method and system for testing filter rules. The present invention addresses such a need.
The present invention provides a method and system for testing a plurality of filter rules in a computer system. The plurality of filter rules are used with a key that is capable of matching at least one filter rule of the plurality of filter rules. The at least one filter rule corresponds to at least one action. The computer system includes a cache and a decision tree. The cache includes a plurality of bins. The method and system comprise searching a plurality of stored keys in the cache for the key. A plurality of stored filter rules corresponds to the plurality of stored keys. A plurality of stored actions corresponds to the plurality of stored filter rules. The cache stores each of the plurality of stored keys and at least one stored action of the plurality of stored actions in each bin of a portion of the plurality of bins. The method and system also comprise obtaining the at least one action from the plurality of stored actions in the cache if the key is found in plurality of stored keys of the cache and obtaining the at least one action using the decision tree if the key is not found in the plurality of stored keys in the cache.
According to the system and method disclosed herein, the present invention can rapidly and simply determine whether a key matches a filter rule by utilizing the information stored in the cache and initially obtained often at great computational expense.